import java.util.*;

class CustomFunction {
    // Returns f(x, y) for any given positive integers x and y.
    // Note that f(x, y) is increasing with respect to both x and y.
    // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
    public int f(int x, int y){
        return 0;
    }
 };
public class project {
    public int numberOfSubarrays(int[] nums, int k) {
        int left=0;
        int right=0;
        int odd=0;
        int ret=0;
        while (right<nums.length){
            if(nums[right++]%2==1){
                odd++;
                right++;
            }
            if(odd==k){
                int tmp=right;
                while (right<nums.length&&nums[right]%2==0){
                    right++;
                }
                int r=right-tmp;
                int l=0;
                while (left<nums.length&&nums[left]%2==0){
                    l++;
                    left++;
                }
                ret+=(l+1)*(r+1);
                left++;
                odd--;
            }
        }
        return ret;
    }



















    public int maximumTop(int[] nums, int k) {
        int len=nums.length;
        int max=0;
        if(len==k%2){
            return -1;
        }
        for(int i=0;i<Math.min(k-1,len);i++){
            max=Math.max(nums[i],max);
        }
        return Math.max(max,k<len?nums[k]:0);
    }



















    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> list=new ArrayList<>();
        int len=(1<<n)-1;
        boolean[] booleans=new boolean[len+2];
        list.add(start);
        booleans[start]=true;
        dfs(list,booleans,start,n,len);
        return list;
    }
    public void dfs(List<Integer> list,boolean[] booleans,int start,int n,int len){
        if(list.size()==len){
            booleans[len+1]=true;
        }
        for(int i=0;i<n;i++){
            int value=start^(1<<i);
            if(booleans[value]){
                continue;
            }
            list.add(value);
            booleans[value]=true;
            dfs(list,booleans,value,n,len);
            if(booleans[len+1]){
                return;
            }
            booleans[n]=false;
            list.remove(list.size()-1);
        }
    }


















    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> list=new ArrayList<>();
        int left=1;
        int right=1000;
        while (left<=1000&&right>=1){
            int tmp=customfunction.f(left,right);
            if(tmp==z){
                list.add(Arrays.asList(left,right));
                left++;
            }else if(tmp>z){
                right--;
            }else{
                left++;
            }
        }
        return list;
    }














    public int findKthNumber(int n, int k) {
        long cur=1;
        k-=1;
        while (k>0){
            int nodes=getNodes(n,cur);
            if(k>=nodes){
                k-=nodes;
                cur++;
            }else{
                k--;
                cur*=10;
            }
        }
        return (int)cur;
    }
    public int getNodes(int n,long cur){
        long nodes=0;
        long next=cur+1;
        while (cur<=n){
            nodes+=Math.min(n-cur+1,next-cur);
            cur*=10;
            next*=10;
        }
        return (int)nodes;
    }
}
